[Overview] [Previous] [Next]

Closure IV: Homomorphism

Note: "Homomorphism" is a term borrowed from group theory. What we refer to as a "homomorphism" is really a special case.

Suppose sigma and gamma are alphabets (not necessarily distinct). Then a homomorphism h is a function from sigma to gamma *.

If w is a string in sigma , then we define h(w) to be the string obtained by replacing each symbol x is a member of sigma by the corresponding string h(x) gamma *.

If L is a language on sigma , then its homomorphic image is a language on gamma . Formally,

h(L) = {h(w): w is a member of

Theorem. If L is a regular language on sigma , then its homomorphic image h(L) is a regular language on gamma . That is, if you replaced every string w in L with h(w), the resultant set of strings would be a regular language on gamma .

Proof.

Construct a dfa representing L. This is possible because L is regular.
For each arc in the dfa, replace its label x with h(x) .
If an arc is labeled with a string w of length greater than one, replace the arc with a series of arcs and (new) states, so that each arc is labeled with a single element of . The result is an nfa that recognizes exactly the language h(L).
Since the language h(L) can be specified by an nfa, the language is regular. Q.E.D.